package com.dragon.datastructure.linkedlist;

/**
 * 删除链表的倒数第N个节点
 *
 * @author dragon
 * @since 2019/12/20
 */
public class Test12 {

    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
            next = null;
        }
    }

    /**
     * 删除链表的倒数第N个节点
     *
     * @param head 头节点
     * @param n    倒数第几个
     * @return 头节点
     */
    public static Node removeNthFromEnd(Node head, int n) {
        Node dummy = new Node(-1);
        dummy.next = head;
        Node first = dummy;
        Node second = dummy;
        for (int i = 1; i <= (n + 1); i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;

        return dummy.next;
    }
}
